﻿// 2896. 执行操作使两个字符串相等.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
/*
https://leetcode.cn/problems/apply-operations-to-make-two-strings-equal/description/

给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。

你可以对字符串 s1 执行以下操作 任意次 ：

选择两个下标 i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。
选择满足 i < n - 1 的下标 i ，反转 s1[i] 和 s1[i + 1] ，操作的代价为 1 。
请你返回使字符串 s1 和 s2 相等的 最小 操作代价之和，如果无法让二者相等，返回 -1 。

注意 ，反转字符的意思是将 0 变成 1 ，或者 1 变成 0 。



示例 1：

输入：s1 = "1100011000", s2 = "0101001010", x = 2
输出：4
解释：我们可以执行以下操作：
- 选择 i = 3 执行第二个操作。结果字符串是 s1 = "1101111000" 。
- 选择 i = 4 执行第二个操作。结果字符串是 s1 = "1101001000" 。
- 选择 i = 0 和 j = 8 ，执行第一个操作。结果字符串是 s1 = "0101001010" = s2 。
总代价是 1 + 1 + 2 = 4 。这是最小代价和。
示例 2：

输入：s1 = "10110", s2 = "00011", x = 4
输出：-1
解释：无法使两个字符串相等。


提示：

n == s1.length == s2.length
1 <= n, x <= 500
s1 和 s2 只包含字符 '0' 和 '1' 。
*/

class Solution {
public:
    int costx = 0;
    string a, b;
    vector<vector<vector<int>>> dp;
    //int dp[510][510][2];
    int dfs(int idx, int revX, int prevRev) {
        if (idx < 0 && (revX > 0 || 1 == prevRev)) {
            return 0x3f3f3f3f/2;   
        }
        else if (idx < 0 && 0 == revX && 0 == prevRev) {
            return 0;
        }

        if (dp[idx][revX][prevRev] != 0x3f3f3f3f) {
            return dp[idx][revX][prevRev];
        }

        int& res = dp[idx][revX][prevRev];
        res = 0x3f3f3f3f;
        if (a[idx] == b[idx] && prevRev == 0) {
            res = dfs(idx - 1, revX, 0);
            return res;
        }
        //两者不相等 或者相等但是有上一步的翻转？
        if (a[idx] != b[idx] && prevRev == 1) {
            res = dfs(idx - 1, revX, 0);
            return res;
        }

        //否则三种选择 第一种操作  第二种操作 之前已经有花费x的翻转 这次免费
        int ret1 = dfs(idx - 1, revX + 1, 0) + costx;
        int ret2 = dfs(idx - 1, revX, 1) + 1;
        int ret3 = 0x3f3f3f3f;
        if (revX > 0)
            ret3 = dfs(idx - 1, revX - 1, 0);

        res = min(ret1, min(ret2, ret3));
        return res;
    }

    int minOperations(string s1, string s2, int x) {
        int diff = 0;
        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s2[i]) diff++;
        }
        if (diff % 2 != 0) return -1;

        int n = s1.size();


        //memset(dp, -1, sizeof dp);
        dp.resize(n + 10, vector<vector<int>>(n + 10, vector<int>(2, 0x3f3f3f3f)));

        costx = x;
        a = s1, b = s2;
        int ret = dfs(n - 1, 0, 0);

        return ret;
    }
};

#if 0
class Solution {
public:
    int minOperations(string s1, string s2, int x) {
        vector<int> p;  p.push_back(-1);

        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s2[i]) { p.push_back(i); }
        }
        if (p.size() % 2 == 0) return -1;

        int dp[510][2]; memset(dp, 0x3f, sizeof dp);

        dp[0][0] = 0;

        for (int i = 1; i < p.size(); i++) {
            if (i % 2 == 0) {
                dp[i][0] = min(dp[i - 1][0] + p[i] - p[i - 1], dp[i - 1][1]);
                dp[i][1] = dp[i - 1][1];
            }
            else {
                dp[i][1] = min(dp[i - 1][0] + x, dp[i - 1][1] + p[i] - p[i - 1]);
                dp[i][0] = dp[i - 1][0];
            }
        }


        cout << dp[p.size() - 1][0] << endl;

        return  dp[p.size() - 1][0];
    }
};
#endif

int main()
{
    Solution s;
    cout <<s.minOperations("11111001100111101010101010100000010000000010110100111000001100101100000010000011100","11101101001010101001000110010101011001100110011011001101100100101101100101100000010",20);



}

 